% This is "sig-alternate.tex" V1.8 June 2007
% This file should be compiled with V2.3 of "sig-alternate.cls" June 2007
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.3 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.3) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@acm.org)
% ===============================================================
%
% For tracking purposes - this is V1.8 - June 2007

\documentclass{sig-alternate}
\usepackage{amsmath,amssymb}
\usepackage[usenames,dvipsnames]{pstricks}
\usepackage{pstricks-add}
\usepackage{graphics}
\usepackage{epsfig}
\usepackage{pst-grad} % For gradients
\usepackage{pst-plot} % For axes
\begin{document}
%
% --- Author Metadata here ---
\conferenceinfo{WOODSTOCK}{'97 El Paso, Texas USA}
%\CopyrightYear{2007} % Allows default copyright year (200X) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

\title{Outline for the upcoming {\ttlit ACM} IPSN conference submission \titlenote{(Produces the permission block, and
copyright information). For use with
SIG-ALTERNATE.CLS. Supported by ACM.}}
\subtitle{[Extended Abstract]
\titlenote{A full version of this paper is available as
\textit{Author's Guide to Preparing ACM SIG Proceedings Using
\LaTeX$2_\epsilon$\ and BibTeX} at
\texttt{www.acm.org/eaddress.htm}}}
%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{3} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
%\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
%\alignauthor
%Ben Trovato\titlenote{Dr.~Trovato insisted his name be first.}\\
%       \affaddr{Institute for Clarity in Documentation}\\
%       \affaddr{1932 Wallamaloo Lane}\\
%       \affaddr{Wallamaloo, New Zealand}\\
%       \email{trovato@corporation.com}
%% 2nd. author
%\alignauthor
%G.K.M. Tobin\titlenote{The secretary disavows
%any knowledge of this author's actions.}\\
%       \affaddr{Institute for Clarity in Documentation}\\
%       \affaddr{P.O. Box 1212}\\
%       \affaddr{Dublin, Ohio 43017-6221}\\
%       \email{webmaster@marysville-ohio.com}
%% 3rd. author
%\alignauthor Lars Th{\o}rv{\"a}ld\titlenote{This author is the
%one who did all the really hard work.}\\
%       \affaddr{The Th{\o}rv{\"a}ld Group}\\
%       \affaddr{1 Th{\o}rv{\"a}ld Circle}\\
%       \affaddr{Hekla, Iceland}\\
%       \email{larst@affiliation.org}
%\and  % use '\and' if you need 'another row' of author names
%% 4th. author
%\alignauthor Lawrence P. Leipuner\\
%       \affaddr{Brookhaven Laboratories}\\
%       \affaddr{Brookhaven National Lab}\\
%       \affaddr{P.O. Box 5000}\\
%       \email{lleipuner@researchlabs.org}
%% 5th. author
%\alignauthor Sean Fogarty\\
%       \affaddr{NASA Ames Research Center}\\
%       \affaddr{Moffett Field}\\
%       \affaddr{California 94035}\\
%       \email{fogartys@amesres.org}
%% 6th. author
%\alignauthor Charles Palmer\\
%       \affaddr{Palmer Research Laboratories}\\
%       \affaddr{8600 Datapoint Drive}\\
%       \affaddr{San Antonio, Texas 78229}\\
%       \email{cpalmer@prl.com}
%}
%% There's nothing stopping you putting the seventh, eighth, etc.
%% author on the opening page (as the 'third row') but we ask,
%% for aesthetic reasons that you place these 'additional authors'
%% in the \additional authors block, viz.
%\additionalauthors{Additional authors: John Smith (The Th{\o}rv{\"a}ld Group,
%email: {\texttt{jsmith@affiliation.org}}) and Julius P.~Kumquat
%(The Kumquat Consortium, email: {\texttt{jpkumquat@consortium.net}}).}
%\date{30 July 1999}
%% Just remember to make sure that the TOTAL number of authors
%% is the number that will appear on the first page PLUS the
%% number that will appear in the \additionalauthors section.

\maketitle
\begin{abstract}
%This paper provides a sample of a \LaTeX\ document which conforms,
%somewhat loosely, to the formatting guidelines for
%ACM SIG Proceedings. It is an {\em alternate} style which produces
%a {\em tighter-looking} paper and was designed in response to
%concerns expressed, by authors, over page-budgets.
%It complements the document \textit{Author's (Alternate) Guide to
%Preparing ACM SIG Proceedings Using \LaTeX$2_\epsilon$\ and Bib\TeX}.
%This source file has been written with the intention of being
%compiled under \LaTeX$2_\epsilon$\ and BibTeX.
%
%The developers have tried to include every imaginable sort
%of ``bells and whistles", such as a subtitle, footnotes on
%title, subtitle and authors, as well as in the text, and
%every optional component (e.g. Acknowledgments, Additional
%Authors, Appendices), not to mention examples of
%equations, theorems, tables and figures.
%
%To make best use of this sample document, run it through \LaTeX\
%and BibTeX, and compare this source code with the printed
%output produced by the dvi file. A compiled PDF version
%is available on the web page to help you with the
%`look and feel'.
\end{abstract}

% A category with the (minimum) three required fields
%\category{H.4}{Information Systems Applications}{Miscellaneous}
%A category including the fourth, optional field follows...
%\category{D.2.8}{Software Engineering}{Metrics}[complexity measures, performance measures]

%\terms{Delphi theory}

%\keywords{ACM proceedings, \LaTeX, text tagging}

\section{Introduction}

\begin{itemize}
	\item Description and challenges associated with the Mobile millennium project
	\item Traditional sensors vs. mobile sensors
	\item Traffic estimation vs. prediction
	\item Arterial vs. Highway state estimation
	\item Arterial models: data driven vs. mechanistic
\end{itemize}


An urban arterial network consists of several arterial links aligned in a geo-spatial manner forming a grid network. These arterial networks can be represented by major and minor streets crossing each other, which are usually categorized from class~$1$ to class~$5$ [HCM]. The crossings, known as \emph{intersections}, are signalized to operate and control flow in the network. An \emph{arterial link} is defined as the length of the road that begins at the end of a signalized intersection and extends through (and includes) the next signalized intersection. In many cases, the link can be a two-way link. An \emph{arterial route} is the set of arterial links which are traversed by a vehicle being in through movement as well as taking left and right turns as required starting from an origin arterial link to the end of its destination arterial link. In the rest of this document, a link means an arterial link and a route means an arterial route.
\begin{figure}
\begin{center}
\scalebox{0.75} % Change this value to rescale the drawing.
{
\begin{pspicture}(0,-0.875)(9.699264,0.835)
\definecolor{color260}{rgb}{0.0,0.0,0.8}
\psline[linewidth=0.02cm](0.089263245,0.0050)(1.6892632,0.0050)
\psline[linewidth=0.02cm](0.089263245,0.405)(1.6892632,0.405)
\psline[linewidth=0.02cm](2.0892632,0.0050)(3.6892633,0.0050)
\psline[linewidth=0.02cm](2.0892632,0.405)(3.6892633,0.405)
\psline[linewidth=0.02cm](2.0892632,0.0050)(2.0892632,-0.415)
\psline[linewidth=0.02cm](1.6892632,0.0050)(1.6892632,-0.415)
\psline[linewidth=0.02cm](2.0892632,0.825)(2.0892632,0.405)
\psline[linewidth=0.02cm](1.6892632,0.825)(1.6892632,0.405)
\psline[linewidth=0.02cm,linestyle=dashed,dash=0.16cm 0.16cm](4.0892634,0.0050)(5.6892633,0.0050)
\psline[linewidth=0.02cm,linestyle=dashed,dash=0.16cm 0.16cm](4.0892634,0.405)(5.6892633,0.405)
\psline[linewidth=0.02cm](4.0892634,0.0050)(4.0892634,-0.415)
\psline[linewidth=0.02cm](3.6892633,0.0050)(3.6892633,-0.415)
\psline[linewidth=0.02cm](4.0892634,0.825)(4.0892634,0.405)
\psline[linewidth=0.02cm](3.6892633,0.825)(3.6892633,0.405)
\psline[linewidth=0.02cm,linestyle=dashed,dash=0.16cm 0.16cm](6.0892634,0.0050)(7.6892633,0.0050)
\psline[linewidth=0.02cm,linestyle=dashed,dash=0.16cm 0.16cm](6.0892634,0.405)(7.6892633,0.405)
\psline[linewidth=0.02cm](6.0892634,0.0050)(6.0892634,-0.415)
\psline[linewidth=0.02cm](5.6892633,0.0050)(5.6892633,-0.415)
\psline[linewidth=0.02cm](6.0892634,0.825)(6.0892634,0.405)
\psline[linewidth=0.02cm](5.6892633,0.825)(5.6892633,0.405)
\psline[linewidth=0.016cm,linecolor=color260,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(0.5092633,0.105)(1.3092632,0.105)
\usefont{T1}{ptm}{m}{n}
\rput(3.887857,0.195){\psovalbox[linewidth=0.04]{$2$}}
\usefont{T1}{ptm}{m}{n}
\rput(1.8561382,0.175){\psovalbox[linewidth=0.04]{$1$}}
\psline[linewidth=0.02cm](8.089263,0.0050)(9.689263,0.0050)
\psline[linewidth=0.02cm](8.089263,0.405)(9.689263,0.405)
\psline[linewidth=0.02cm](8.089263,0.0050)(8.089263,-0.415)
\psline[linewidth=0.02cm](7.6892633,0.0050)(7.6892633,-0.415)
\psline[linewidth=0.02cm](8.089263,0.825)(8.089263,0.405)
\psline[linewidth=0.02cm](7.6892633,0.825)(7.6892633,0.405)
\usefont{T1}{ptm}{m}{n}
\rput(7.880357,0.195){\psovalbox[linewidth=0.04]{$I$}}
\usefont{T1}{ptm}{m}{n}
\rput(5.889576,0.175){\psovalbox[linewidth=0.04]{$i$}}
\psline[linewidth=0.016cm,linecolor=color260,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(8.729263,0.105)(9.5292635,0.105)
\psframe[linewidth=0.04,linecolor=red,dimen=outer](2.4892633,0.405)(2.4692633,0.0050)
\psframe[linewidth=0.04,linecolor=red,dimen=outer](4.489263,0.405)(4.469263,0.0050)
\psframe[linewidth=0.04,linecolor=red,dimen=outer](0.28926325,0.405)(0.26926324,0.0050)
\psframe[linewidth=0.04,linecolor=red,dimen=outer](6.489263,0.405)(6.469263,0.0050)
\psframe[linewidth=0.04,linecolor=red,dimen=outer](8.489264,0.405)(8.469263,0.0050)
\psline[linewidth=0.012cm,tbarsize=0.07055555cm 5.0,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{|*->}(0.28926325,-0.495)(2.4892633,-0.495)
\psline[linewidth=0.012cm,tbarsize=0.07055555cm 5.0,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{|*->}(2.4892633,-0.495)(4.509263,-0.495)
\psline[linewidth=0.012cm,tbarsize=0.07055555cm 5.0,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{|*->}(4.489263,-0.495)(6.509263,-0.495)
\psline[linewidth=0.012cm,tbarsize=0.07055555cm 5.0,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{|*->}(6.469263,-0.495)(8.5292635,-0.495)
\usefont{T1}{ptm}{m}{n}
\rput(1.4436382,-0.725){$L_1$}
\usefont{T1}{ptm}{m}{n}
\rput(3.4581695,-0.725){$L_2$}
\usefont{T1}{ptm}{m}{n}
\rput(5.4012947,-0.725){$L_i$}
\usefont{T1}{ptm}{m}{n}
\rput(7.4112945,-0.725){$L_I$}
\psline[linewidth=0.0080cm,linestyle=dotted,dotsep=0.16cm](0.089263245,0.205)(9.689263,0.205)
\psline[linewidth=0.016cm,linecolor=color260,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(1.2892632,0.305)(0.48935908,0.2962448)
\psline[linewidth=0.016cm,linecolor=color260,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(9.489264,0.305)(8.689359,0.2962448)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(1.9692632,0.485)(1.9692632,0.805)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(1.7692633,0.805)(1.7692633,0.505)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(3.9892633,0.485)(3.9892633,0.805)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(3.8092632,0.805)(3.8092632,0.505)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(5.7892632,0.785)(5.7892632,0.485)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(5.989263,0.485)(5.989263,0.805)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(7.7892632,0.805)(7.7892632,0.505)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(7.989263,0.485)(7.989263,0.805)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(1.7692633,-0.095)(1.7692633,-0.395)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(1.9692632,-0.395)(1.9692632,-0.075)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(3.7892632,-0.095)(3.7892632,-0.395)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(3.9892633,-0.395)(3.9892633,-0.075)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(5.809263,-0.095)(5.809263,-0.395)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(6.009263,-0.395)(6.009263,-0.075)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(7.7892632,-0.095)(7.7892632,-0.395)
\psline[linewidth=0.016cm,linecolor=blue,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(7.989263,-0.395)(7.989263,-0.075)
\usefont{T1}{ptm}{m}{n}
\rput{-1.397858}(-0.014836207,0.007901893){\rput(0.30270076,0.63){\footnotesize $s_{0}$}}
\usefont{T1}{ptm}{m}{n}
\rput{-1.397858}(-0.013693597,0.06156451){\rput(2.5027008,0.61){\footnotesize $s_{1}$}}
\usefont{T1}{ptm}{m}{n}
\rput{-1.397858}(-0.013080546,0.11181781){\rput(4.5627007,0.61){\footnotesize $s_{i-1}$}}
\usefont{T1}{ptm}{m}{n}
\rput{-1.397858}(-0.012515111,0.15816793){\rput(6.462701,0.61){\footnotesize $s_{i}$}}
\usefont{T1}{ptm}{m}{n}
\rput{-1.397858}(-0.012389956,0.20842718){\rput(8.5227,0.63){\footnotesize $s_{I}$}}
\end{pspicture} 
}
\end{center}
\label{fig:inter}
\caption{Representation of arterial links.}
\end{figure}


%\begin{figure}[htbp]
%   \centering
%   \includegraphics[scale=0.5]{inter} % requires the graphicx package
%   \caption{Representation of arterial links and intersections.}
%   \label{fig:inter}
%\end{figure}
The link and intersection representations adopted in this study are denoted in Figure~\ref{fig:inter}. A link~$l_{i}$ is associated to an intersection~$i$. We assume that the route has a total of $I$ intersections. Each link can be equipped with one or more point sensors such as loop detectors and \textit{virtual trip lines} (VTLs). This study is for VTL sensors. A VTL can be thought of as virtual point sensor (without any physical infrastructure) with a pre-selected location on the route. When a GPS equipped mobile device, in this case a cell-phone, passes a VTL, the sensor logs the time tagged speed, position measurement and eventually additional information related to traffic on that arterial. To preserve the privacy of mobile device owners, the identity of the phone user in the vehicle is stripped from the transmitted data. For a route with~$m$ VTLs per link, we have~$mI$ sensors if the route is open and $N=(mI-1)$ sensors if the route is closed. We assume that any link~$l_{i}$ has an upstream VTL~$u_{i}$, a downstream VTL~$d_{i}$ and possibly, intermediate VTLs~$m_{i}$ located at the middle of the link. 

The sensor data collected by GPS equipped cell phones is geographically based as shown in Table~\ref{tab:dataformat}. An event~$k$ is marked by the time a vehicle passes over a VTL~$j$, denoted by $T^{k}$. The data we obtain is individual vehicle speed at the current VTL, denoted by~$v_{j}^{k}$ and the individual vehicle travel time between the current VTL and the previous VTL, denoted by~$tt_{j'\rightarrow j}^{k}$. Here, $j'$ is the VTL that the vehicle crossed just before crossing VTL~$j$. 
\begin{table}[htbp]
\scalebox{0.75} {
	\centering
		\begin{tabular}{l | c | c | c}
			\hline\hline
			Event ID & Event description  & Inst.veh.vel. & Veh.Travel time \\ \hline
			$1$ & VTL $1$ is crossed at time $T^{1}_{1}$ & $v_{1}^1$ & $tt_{0\rightarrow 1}^1$ \\ \hline
			$\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ \\ \hline
			$k$ & VTL $j$ is crossed at time $T^k_{j}$ & $v_{j}^k$ &  $tt_{j'\rightarrow j}^k$ \\ \hline
			$\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ \\ \hline
		\end{tabular}
		}
	\caption{Event based mobile sensor data.}
	\label{tab:dataformat}
\end{table}
Note that the individual vehicle travel times should be distinguished from average travel time which is the average of travel times incurred by the individual vehicles if each vehicle can be tracked on a link. We denote the average travel time for the link~$i$ during time period~$\tau$ by~$TT_{i}(\tau)$; the individual vehicle travel time for the link~$i$ during time period~$\tau$ by $tt_{i}(\tau)$. The individual vehicle travel times~$tt_{i}{\tau}$ can be computed by aggregating the travel times~$tt_{j'\rightarrow j}$ for consecutive detector locations in the same link. We omit the details of this aggregation. 

If all the vehicles on a link are equipped with GPS phones, then we have
\[TT_{i}(\tau)=\frac{\sum_{i}tt_{i}(\tau)}{\text{\# of vehicles in section}~i \text{ during}~\tau},\]
where the summation is carried over all the vehicles present in the section~$i$ during time interval~$\tau$.

However, with current penetration rate of GPS equipped cellular phones, data from only a certain percentage of vehicles is available for travel time estimation. Typically, the penetration rate is less than $5\%$. Thus, unless all the vehicles are equipped with GPS phones, the quantity $TT_{i}(\tau)$ is unknown. 
In order to obtain reasonably accurate estimates of average travel times for individual links as well as for a whole route, we need a \emph{model based estimation} procedure as shown in Figure~\ref{fig:estimator}. This is the aim of the present document.

\begin{figure}
\centering
{
\begin{pspicture}(0,-0.92828125)(7.6409373,0.92828125)
\definecolor{color12b}{rgb}{0.8,0.8,1.0}
\psframe[linewidth=0.04,dimen=outer,fillstyle=solid,fillcolor=color12b](5.14875,0.69203126)(1.58875,-0.68796873)
\usefont{T1}{ptm}{m}{n}
\rput(3.3560936,0.00203125){Model based estimator}
\psline[linewidth=0.04cm,fillcolor=color12b,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(0.74875,0.47203124)(1.60875,0.45203125)
\psline[linewidth=0.04cm,fillcolor=color12b,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(0.74875,0.01203125)(1.60875,-0.00796875)
\psline[linewidth=0.04cm,fillcolor=color12b,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(0.74875,-0.42796874)(1.60875,-0.44796875)
\psline[linewidth=0.04cm,fillcolor=color12b,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(5.14875,0.01203125)(6.00875,-0.00796875)
\usefont{T1}{pcr}{m}{n}
\rput(0.23953125,0.56203127){$tt_{j'\rightarrow j}^{k}$}
\usefont{T1}{pcr}{m}{n}
\rput(0.20984375,-0.59796876){ $T_{j}^{k}$}
\usefont{T1}{pcr}{m}{n}
\rput(0.20796876,0.04203125){ $v_{j}^{k}$}
\usefont{T1}{pcr}{m}{n}
\rput(6.5,0.00203125){ $TT_{i}(\tau)$}
\usefont{T1}{pcr}{m}{n}
\end{pspicture} 
}
\normalsize
\caption{Input and outputs to the estimator.}
    \label{fig:estimator}
\end{figure}
We denote the \emph{estimated average travel time} for the link~$i$ during time period~$\tau$ by~$\hat{TT}_{i}(\tau)$. The error in travel time for link~$i$ during time period~$\tau$ is given by~\eqref{eq:err}.
\begin{align}
e_{i}(\tau)=\hat{TT}_{i}(\tau)-TT_{i}(\tau)
\label{eq:err}
\end{align}
One of the commonly chosen metric for the performance of any estimator is the reduction in the error variance as compared to simple mean. 

Before moving further, we will elaborate upon the difficulty in adopting the simple weighted average method for travel time estimation. This method was proposed by Sanwal and Walrand for estimating travel times on freeways~\cite{SanwalWalrand}. Let $n_{i}(\tau)$ be the number of individual vehicle travel time estimates of link~$i$ during time~$\tau$. Then the new estimate of $\hat{TT}_{i}(\tau)$ can be computed as a weighted average of the sample mean and the previous estimate:
\begin{align}
\hat{TT}_{i}(\tau)=(1-\alpha_{i}(\tau))\hat{TT}_{i}(\tau-1)+\alpha_i(\tau)\frac{1}{n_{i}(\tau)}\sum_{j=1}^{n_{i}(\tau)}tt_{i}^{j}(\tau), && \alpha_{i}(\tau)\in(0,1],
\label{eq:weightedavg}
\end{align}
where $\alpha_{i}^{j}$ is a weight selected in order to minimize the mean squared estimation error~\cite{SanwalWalrand}. 

However, as described in \cite{skagero05a}, the travel time for a link is a nonlinear function of the signal timing, the downstream congestion status, flow through cross-streets, and the upstream queue length for the case of arterials. Without taking into account these variables, the weighted averaging scheme is expected to incur significant error. Therefore, a sound estimation method for arterials should be based on reasonably accurate model of the traffic flow phenomenon. This leads us to the classic estimability (observability) vs. complexity trade off, i.e., the more complex the model gets, it is likely to require more data for obtaining reliable estimates. 
%
%Travel time is an important indicator of quality-of-service (QoS) of an arterial network. It is important to distinguish between the travel time of an individual vehicle and travel time of the vehicle stream passing through the link. 
\subsection{Notation}
We now list the notation used in this document. The three quantities of interest to us are the following: the travel time of link~$i$ during time interval~$\tau$ denoted by $TT_{i}(\tau)$, the queue length upstream of intersection~$i$ during time interval~$\tau$ denoted by $L_{q,i}(\tau)$, and the delay at the intersection~$i$ during time interval~$\tau$ denoted by~$d_{i}(\tau)$. The quantities $TT_{i}(\tau)$ and $d_{i}(\tau)$ are related as
\[TT_{i}(\tau)=TT_{i}^{ff}+d_{i}(\tau),\]
where $TT_{i}^{ff}$ is the free-flow travel time or the time a vehicle needs to travel the length of the link~$i$ without interference from the presence of an intersection. Thus,
\[TT_{i}^{ff}=\frac{L_{i}}{v_{f,i}}\]
where $v_{f,i}$ is the free-flow speed for the~$i$th link. For route a $A\rightarrow B$ having $I$ intersections, the route travel-time can be expressed as
\begin{align}\label{eq:modelroute}
TT_{A\rightarrow B}^{m}(\tau)=\sum_{i=1}^{I}TT_{i}(\tau)
\end{align}

%
%The parameters of this relationship are listed in Table~\ref{tab:fundamental}.
%\begin{table}[htbp]
%	\centering
%		\begin{tabular}{l | c}
%			\hline\hline
%			Parameter description & Notation \\ \hline
%			Free flow speed & $v_{f}$			  \\ \hline
%			Capacity & $F$  \\ \hline
%			Jam density & $k_{j}$  \\ \hline
%			Critical density & $k_{c}$  \\ \hline
%			Congested wave speed & $u_w$  \\ \hline
%		\end{tabular}
%	\caption{Parameters of the fundamental diagram.}
%	\label{tab:fundamental}
%\end{table}
\begin{figure}
\begin{center}
\scalebox{1.5} % Change this value to rescale the drawing.
{
\begin{pspicture}(0,-1.3629167)(2.6658332,1.3629167)
\rput(0.66583335,-0.63708335){\psaxes[linewidth=0.016,arrowsize=0.1cm 2.0,arrowlength=1.4,arrowinset=0.4,labels=none,ticks=y,ticksize=0.10583333cm,dx=0.55cm,dy=1.0cm]{->}(0,0)(0,0)(2,2)}
\psline[linewidth=0.016cm,linecolor=blue](0.66183335,-0.63708335)(1.2818333,0.38291666)
\psline[linewidth=0.016cm,linecolor=blue](1.2818333,0.38291666)(2.2618334,-0.63708335)
\psline[linewidth=0.01cm](1.5818334,0.062916666)(1.7818333,0.062916666)
\psline[linewidth=0.01cm](1.7818333,0.062916666)(1.7818333,-0.13708334)
\psline[linewidth=0.01cm](0.92183334,0.102916665)(1.1018333,0.102916665)
\psline[linewidth=0.01cm](0.92183334,0.102916665)(0.92183334,-0.19708334)
\psline[linewidth=0.0060cm,linestyle=dashed,dash=0.16cm 0.16cm](0.8818333,-0.25708333)(2.2618334,-0.63708335)
\psline[linewidth=0.0040cm](1.2618333,-0.35708332)(1.5618334,-0.35708332)
\psline[linewidth=0.01cm](1.5618334,-0.35708332)(1.5618334,-0.45708334)
\usefont{T1}{ptm}{m}{n}
\rput(0.46167707,0.35791665){\tiny $F$}
\usefont{T1}{ptm}{m}{n}
\rput(0.47652084,-0.22208333){\tiny $q$}
\psline[linewidth=0.0020cm](0.66183335,-0.25708333)(0.90183336,-0.25708333)
\psline[linewidth=0.0020cm](0.66183335,0.36291668)(1.3018333,0.36291668)
\psline[linewidth=0.005cm](1.2818333,0.38291666)(1.2818333,-0.63708335)
\usefont{T1}{ptm}{m}{n}
\rput(1.3262084,-0.78208333){\tiny $k_c$}
\usefont{T1}{ptm}{m}{n}
\rput(2.251677,-0.78208333){\tiny $k_j$}
\usefont{T1}{ptm}{m}{n}
\rput(1.9857396,-0.022083335){\tiny $u_w$}
\usefont{T1}{ptm}{m}{n}
\rput(1.6883959,-0.34208333){\tiny $u_s$}
\usefont{T1}{ptm}{m}{n}
\rput(0.8,-0.042083334){\tiny $v_f$}
\end{pspicture} 
}
\end{center}
\label{fig:fund}
\caption{Flow-density diagram}
\end{figure}


Oftentimes, it is possible to obtain signal timing parameters. When available, these parameters can dramatically improve the estimation accuracy. We list the signal parameters in Table~\ref{tab:signalparam}
\begin{table}[htbp]
	\centering
		\begin{tabular}{l | c}
			\hline\hline
			Parameter description & Notation \\ \hline
			Cycle time & $c$			  \\ \hline
			Effective green time & $g$  \\ \hline
			Effective red time & $r$  \\ \hline
			Effective green proportion & $\lambda g/c$  \\ \hline			
		\end{tabular}
	\caption{Signal timing parameters.}
	\label{tab:signalparam}
\end{table}


Results from the kinematic wave theory (or LWR theory) can be used to derive equations for queue lengths and hence the delay caused due to presence of queues at an intersection. We assume a piecewise linear flow-density relationship with parameters~$v_{f}$ (free-flow speed), $F$ (capacity), $k_{j}$ (jam density), $u_{w}$ (congested wave speed) as shown in Figure~\ref{fig:fund}. Refering to Figure~\ref{fig:xtdiag},~$L_{p}$ is the distance at which the queuing delay is maximum and~$L_{q}$ is the farthest point until which the queue extends.  It is easy to show that
\begin{align*}
L_{p}=r\left[\frac{v_{f}\cdot u_{s}}{v_{f}+u_{s}}\right], && L_{q}=r\left[\frac{u_{s}\cdot u_{w}}{u_{w}-u_{s}}\right]
\end{align*}
where $u_{s}$ is the ratio of the arrival flow rate~$q$ and difference $(k_{j}-k)$. Let $t_{0}$ be the time at which a hypothetical vehicle that is destined to arrive at the intersection just at the start of the red time is at~$L_{q}$ distance upstream of the intersection. The time $t_{c}$ at which the queue has cleared can be expressed as
\[t_{c}=t_{0}+L_{q}\left[\frac{1}{v_{f}}+\frac{1}{u_{s}}\right]\]
and the expression of the delay $d(t)=TT(t)-TT^{ff}$ for a single cycle is
\begin{align}\label{eq:delaysingle}
d(t)=\begin{cases}
r-\frac{v_{f}}{u_{w}}\left[\frac{u_{w}-u_{s}}{v_{f}+u_{s}}\right](t-t_{0}) \mbox{ for } t_{0}\leq t<t_c\\
0 \mbox{ for } t\geq t_{c}
\end{cases}
\end{align}

\subsection{Our Approach}

\begin{itemize}
	\item Directly measuring (empirical) travel time distributions
	\item Availability and privacy constraints
	\item Data description and concept of VTLs
	\item Starting from data driven point of view but consistent with mechanistic thinking
	\item System architecture: Three tier architecture with outlier detection and data preprocessing, travel time estimation, and confidence interval and validation testing
\end{itemize}

For route a $A\rightarrow B$ having $I$ intersections, a naive estimate of the travel time is 
\begin{align}\label{eq:naiveroute}
TT_{A\rightarrow B}^{n}(\tau)=\sum_{i=1}^{I}(TT_{i}^{ff}+\delta_{i}^{\mbox{avg}}(\tau))
\end{align}
for $\tau=0,1,2,\ldots,$ where $\delta_{i}^{\mbox{avg}}(\tau))$ is the estimate of the delay caused to traverse the link~$i$ (that is associated with intersection~$i$) computed using a naive method such as: weighted average, exponential smoothing, or interpolation. Let $d_{i}(\tau)\in(0,d_{i}^{\max}]$ is the \emph{unknown} delay caused to traverse link~$i$ during the time interval~$\tau$. The \emph{mode} of link~$i$ is given by $m_{i}(\tau)\in\mathcal{M}$. The mode of link~$i$ evolves as
\begin{align}\label{eq:modeevol}
m_{i}(\tau+1)=f(m_{i-1}(\tau), m_{i}(\tau), m_{i+1}(\tau), w_{i}(\tau))
\end{align}
where $(i-1)$ and $(i+1)$ denote the upstream and the downstream links respectively for link~$i$, and $w_{i}(\tau)$ denote the exogeneous inputs for link~$i$ during time $\tau$. The delay in link~$i$ evolves as
\begin{align}\label{eq:delayevol}
d_{i}(\tau+1)=g(d_{i}(\tau),m_{i}(\tau),\xi_{i}(\tau))
\end{align}
The observed travel time measurements can be represented by the meaurement equation
\begin{align}\label{eq:obseq}
tt_{i}(\tau)=h^{a,p}(m_{i}(\tau),d_{i}(\tau),\eta_{i}(\tau))
\end{align}
where $\eta_{i}(\tau)$ denote the measurement noise for~link $i$ during time~$\tau$. The operator~$h^{a,p}$ also encodes the availability and privacy constraints under which the travel time observations become available. At any time $\tau$, the information set available to the estimator is given by 
\begin{align}\label{eq:infoset}
\mathcal{F}(\tau)=\{tt_{i}(0),\ldots,tt_{i}(\tau), i=1,\ldots,I\}
\end{align}
The estimator $\mu_{k}$ computes the estimates $(\hat m_{i}(\tau),\hat d_{i}(\tau))$ using $\mathcal{F}(\tau)$: $\hat d_{i}(\tau)=\mu_{k}(\mathcal{F}_{\tau})$. 


\section{Exploratory analysis of the data}

\begin{itemize}
	\item Measured quantity: individual vehicle travel times
	\item Derived quantities: individual vehicle pace and average speed
	\item Histograms, time-series plots, correlations and cross-correlations
	\item Event based nature, missing data
	\item Presence of non-stationarity, effect of over-saturation
	\item Smoothing vs. averaging vs. interpolation
	\item Naive estimation method: moving average/exponential smoothing
	\item Scope of improving the naive estimation method and motivation for the proposed method
\end{itemize}


\section{Placement of VTLs}
Most of the delay in arterial corridors is experienced upstream intersections, where vehicles are stopped during the red light and a queue forms. The time-space diagram in Figure~\ref{fig:tx_diag} depicts how the queue grows upstream an under-saturated intersection during the red period, and how it vanishes during the green light. In state A the flow is $q_a$, and vehicles are traveling at free flow speed $v_f$. State J represents the queue, where vehicles are stopped. The flow at state C is maximum (capacity), and corresponds to the flow observed during the green light while the queue is discharging. The shockwave with velocity $u_s$ corresponds to the rear end of the queue, while the wave with velocity $u_w$ is the front of the queue (which is at location XX and static during the red light).

If we are interested in measuring the travel time to cross the intersection, one VTL needs to be deployed upstream and downstream the intersection. If the downstream VTL is placed at location $x_d$, the goal is to place the upstream VTL in such a way that most of the delays incurred by the vehicles at the intersection are captured. This would allow us to observed most of the variability in travel times. Intuitively, upstream VTL should be placed at the maximum extend of the queue, which can be seen from Figure~\ref{fig:tx_diag}.
%\begin{figure}[!h]
%  \centering
%  \includegraphics[width=.45\textwidth]{tx.eps}\\
%  \caption{Time space diagram.}
%  \label{fig:tx_diag}
%\end{figure}
\begin{figure}
\centering
\scalebox{0.75} % Change this value to rescale the drawing.
{
\begin{pspicture}(0,-3.4739063)(8.585313,3.4739063)
\definecolor{color4453}{rgb}{0.0,0.8,0.8}
\definecolor{color4560b}{rgb}{0.6,0.0,0.0}
\psline[linewidth=0.03cm,linecolor=red](2.1616876,1.8239244)(5.1398573,1.8239244)
\psline[linewidth=0.03cm,linecolor=OliveGreen](5.137873,1.8239244)(8.1140585,1.8239244)
\psline[linewidth=0.02cm](2.1616876,1.8239244)(7.121997,-2.16686)
\psline[linewidth=0.036cm,linecolor=blue](5.137873,1.8239244)(7.121997,-2.16686)
\psline[linewidth=0.03cm,linecolor=blue](5.137873,1.8239244)(4.8005724,-0.30449402)
\psline[linewidth=0.03cm,linecolor=blue](4.8005724,-0.30449402)(7.121997,-2.16686)
\psline[linewidth=0.0060cm,linecolor=color4453](5.137873,1.8239244)(4.3442235,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](5.0585084,-0.50403327)(4.6418424,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](5.296603,-0.70357245)(4.9196196,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](5.534698,-0.9031117)(5.1775556,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](5.792634,-1.1359074)(5.455333,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](6.05057,-1.3021902)(5.7331104,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](4.542636,-0.07169825)(4.046605,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](2.1815288,1.8239244)(1.3878794,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](2.2410526,3.154186)(1.2291495,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](2.3997824,1.6243852)(1.6458154,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](2.6378772,1.4581025)(1.9037515,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](2.875972,1.2585633)(2.1616876,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](3.114067,1.0922806)(2.3997824,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](3.3323207,0.8927414)(2.6577184,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](7.9950113,3.154186)(6.9632673,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](3.5704155,0.69320214)(2.955337,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](3.8283515,0.4936629)(3.2331145,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](4.0664463,0.29412368)(3.4910505,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](4.3243823,0.09458444)(3.8085103,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](6.8442197,-1.9673209)(6.6656485,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](6.5862837,-1.7677817)(6.348189,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](6.3283477,-1.5017294)(6.05057,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](4.542636,-0.07169825)(6.090253,-0.07169825)
\psline[linewidth=0.0060cm,linecolor=color4453](4.8005724,-0.30449402)(6.189459,-0.30449402)
\psline[linewidth=0.0060cm,linecolor=color4453](5.0585084,-0.50403327)(6.288665,-0.50403327)
\psline[linewidth=0.0060cm,linecolor=color4453](5.296603,-0.70357245)(6.3878713,-0.70357245)
\psline[linewidth=0.0060cm,linecolor=color4453](5.534698,-0.9031117)(6.487077,-0.9031117)
\psline[linewidth=0.0060cm,linecolor=color4453](5.792634,-1.1026509)(6.606125,-1.1026509)
\psline[linewidth=0.0060cm,linecolor=color4453](6.05057,-1.3021902)(6.6854897,-1.3021902)
\psline[linewidth=0.0060cm,linecolor=color4453](6.3283477,-1.5017294)(6.8243785,-1.5017294)
\psline[linewidth=0.0060cm,linecolor=color4453](4.3243823,0.09458444)(5.9910464,0.09458444)
\psline[linewidth=0.01cm,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(1.0902607,-3.1645563)(8.1339,-3.1645563)
\psline[linewidth=0.01cm,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(1.0902607,-3.1645563)(1.0753125,3.1504688)
\psline[linewidth=0.0060cm,linecolor=color4453](4.046605,0.29412368)(5.8719993,0.29412368)
\psline[linewidth=0.0060cm,linecolor=color4453](3.8283515,0.4936629)(5.772793,0.4936629)
\psline[linewidth=0.0060cm,linecolor=color4453](3.5704155,0.69320214)(5.693428,0.69320214)
\psline[linewidth=0.0060cm,linecolor=color4453](3.3124795,0.8927414)(5.5942216,0.8927414)
\psline[linewidth=0.0060cm,linecolor=color4453](3.0942256,1.0590241)(5.4950156,1.0590241)
\psline[linewidth=0.0060cm,linecolor=color4453](2.8561308,1.2585633)(5.4156504,1.2585633)
\psline[linewidth=0.0060cm,linecolor=color4453](2.6378772,1.4581025)(5.296603,1.4581025)
\psline[linewidth=0.0060cm,linecolor=color4453](2.3997824,1.6243852)(5.2172384,1.6243852)
\psline[linewidth=0.0060cm,linecolor=color4453](6.606125,-1.7345252)(6.9037433,-1.7345252)
\psline[linewidth=0.0060cm,linecolor=color4453](6.8442197,-1.9340644)(7.022791,-1.9340644)
\psline[linewidth=0.0060cm,linecolor=color4453](7.81644,3.154186)(7.0029497,-1.9340644)
\psline[linewidth=0.0060cm,linecolor=color4453](7.5188217,3.1874425)(6.784696,-1.5017294)
\psline[linewidth=0.0060cm,linecolor=color4453](7.379933,3.154186)(6.6854897,-1.3021902)
\psline[linewidth=0.0060cm,linecolor=color4453](7.2410445,3.154186)(6.5862837,-1.1026509)
\psline[linewidth=0.0060cm,linecolor=color4453](7.121997,3.154186)(6.487077,-0.86985517)
\psline[linewidth=0.0060cm,linecolor=color4453](7.0029497,3.154186)(6.3878713,-0.70357245)
\psline[linewidth=0.0060cm,linecolor=color4453](7.6775517,3.154186)(6.9037433,-1.7012687)
\psline[linewidth=0.0060cm,linecolor=color4453](6.864061,3.154186)(6.288665,-0.4707767)
\psline[linewidth=0.0060cm,linecolor=color4453](6.725172,3.154186)(6.189459,-0.30449402)
\psline[linewidth=0.0060cm,linecolor=color4453](6.5862837,3.154186)(6.090253,-0.038441714)
\psline[linewidth=0.0060cm,linecolor=color4453](6.447395,3.1874425)(5.971205,0.09458444)
\psline[linewidth=0.0060cm,linecolor=color4453](6.3283477,3.1874425)(5.8918405,0.29412368)
\psline[linewidth=0.0060cm,linecolor=color4453](6.2093,3.154186)(5.792634,0.4936629)
\psline[linewidth=0.0060cm,linecolor=color4453](6.090253,3.1874425)(5.693428,0.69320214)
\psline[linewidth=0.0060cm,linecolor=color4453](5.931523,3.154186)(5.5942216,0.8927414)
\psline[linewidth=0.0060cm,linecolor=color4453](5.812475,3.154186)(5.4950156,1.0590241)
\psline[linewidth=0.0060cm,linecolor=color4453](5.693428,3.154186)(5.395809,1.2585633)
\psline[linewidth=0.0060cm,linecolor=color4453](5.5743804,3.1874425)(5.3164444,1.491359)
\psline[linewidth=0.0060cm,linecolor=color4453](5.455333,3.154186)(5.2370796,1.6243852)
\psline[linewidth=0.0060cm,linecolor=color4453](5.356127,3.1874425)(5.1577144,1.8239244)
\psline[linewidth=0.03cm,linecolor=OliveGreen](1.0902607,1.8239244)(2.1616876,1.8239244)
\psline[linewidth=0.0060cm,linecolor=color4453](8.173583,3.154186)(7.141838,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](8.332313,3.154186)(7.300568,-3.1645563)
\psline[linewidth=0.0060cm,linecolor=color4453](2.1021638,3.1874425)(1.0902607,-3.1312997)
\usefont{T1}{ptm}{m}{n}
\rput(2.3123438,3.3004687){$0$}
\usefont{T1}{ptm}{m}{n}
\rput(5.3621874,3.2804687){$1$}
\usefont{T1}{ptm}{m}{n}
\rput(8.376407,3.3004687){$23$}
\psline[linewidth=0.01cm](0.6553125,1.8304688)(0.9153125,1.8304688)
\psline[linewidth=0.01cm](0.0953125,1.8304688)(0.3553125,1.8304688)
\psline[linewidth=0.01cm](0.6553125,2.0704687)(0.9153125,2.0704687)
\psline[linewidth=0.01cm](0.0953125,2.0704687)(0.3553125,2.0704687)
\psline[linewidth=0.01cm](0.3353125,1.8304688)(0.3353125,-3.1695313)
\psline[linewidth=0.01cm](0.6753125,1.8304688)(0.6753125,-3.1695313)
\psline[linewidth=0.01cm](0.6553125,2.0704687)(0.6553125,3.2304688)
\psline[linewidth=0.01cm](0.3553125,2.0704687)(0.3553125,3.2304688)
\usefont{T1}{ptm}{m}{n}
\rput(0.49984375,1.9354688){\footnotesize {$i$}}
\psline[linewidth=0.01cm,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{<->}(2.1553125,1.9504688)(5.1353126,1.9504688)
\usefont{T1}{ptm}{m}{n}
\rput(3.6353126,2.1204688){$r$}
\usefont{T1}{ptm}{m}{n}
\rput(2.0625,1.9804688){$C$}
\usefont{T1}{ptm}{m}{n}
\rput(5.2753124,1.9804688){$D$}
\usefont{T1}{ptm}{m}{n}
\rput(4.7425,-0.45953125){$B$}
\usefont{T1}{ptm}{m}{n}
\rput(7.221875,-2.2995312){$A$}
\usefont{T1}{ptm}{m}{n}
\rput(3.7425,-0.50953125){\psovalbox[linewidth=0.04]{$\mathbf{I}$}}
\psframe[linewidth=0.01,linecolor=color4560b,dimen=outer,fillstyle=solid,fillcolor=color4560b](0.6753125,-2.1495314)(0.3353125,-2.1795313)
\psframe[linewidth=0.01,linecolor=color4560b,dimen=outer,fillstyle=solid,fillcolor=color4560b](0.6753125,1.8304688)(0.3353125,1.8004688)
\psframe[linewidth=0.01,linecolor=color4560b,dimen=outer,fillstyle=solid,fillcolor=color4560b](0.6753125,2.0904686)(0.3353125,2.0604687)
\psframe[linewidth=0.01,linecolor=color4560b,dimen=outer,fillstyle=solid,fillcolor=color4560b](0.6753125,-0.26953125)(0.3353125,-0.29953125)
\usefont{T1}{ptm}{m}{n}
\rput(0.1725,-2.1395311){$x_a$}
\usefont{T1}{ptm}{m}{n}
\rput(0.15671875,-0.25953126){$x_b$}
\usefont{T1}{ptm}{m}{n}
\rput(0.16703124,1.6804688){$x_c$}
\usefont{T1}{ptm}{m}{n}
\rput(0.1834375,2.2804687){$x_d$}
\psline[linewidth=0.01cm,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{<->}(2.1553125,2.2904687)(8.135312,2.2904687)
\usefont{T1}{ptm}{m}{n}
\rput(5.2832813,2.5404687){$c$}
\psline[linewidth=0.01cm,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{<->}(7.2753124,1.8304688)(7.2953124,-2.1895313)
\usefont{T1}{ptm}{m}{n}
\rput(7.5317187,-0.01953125){$L_q$}
\psline[linewidth=0.0040cm](5.8953123,0.85046875)(5.8953123,0.33046874)
\psline[linewidth=0.0040cm](5.6353126,0.85046875)(5.8953123,0.85046875)
\psline[linewidth=0.0040cm](4.9353123,1.0904688)(5.0353127,1.0904688)
\psline[linewidth=0.0040cm](4.9353123,1.0904688)(4.9353123,0.67046875)
\psline[linewidth=0.0040cm](3.6553125,0.6304687)(3.6553125,0.21046875)
\psline[linewidth=0.0040cm](3.6553125,0.21046875)(4.1753125,0.21046875)
\usefont{T1}{ptm}{m}{n}
\rput(4.722031,0.92046875){$v_f$}
\usefont{T1}{ptm}{m}{n}
\rput(6.1134377,0.6404688){$u_w$}
\usefont{T1}{ptm}{m}{n}
\rput(3.4489063,0.46046874){$u_s$}
\usefont{T1}{ptm}{m}{n}
\rput(8.2239065,-3.1195312){$t$}
\usefont{T1}{ptm}{m}{n}
\rput(1.1207813,3.3204687){$x$}
\psline[linewidth=0.018cm,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{->}(0.5153125,-1.5695312)(0.5153125,-0.94953126)
\psline[linewidth=0.01cm,arrowsize=0.05291667cm 2.0,arrowlength=1.4,arrowinset=0.4]{<->}(4.4953127,1.8304688)(4.4953127,-0.30953124)
\usefont{T1}{ptm}{m}{n}
\rput(3.825625,1.2204687){\psovalbox[linewidth=0.04]{$\mathbf{II}$}}
\usefont{T1}{ptm}{m}{n}
\rput(6.5134377,1.0404688){\psovalbox[linewidth=0.04]{$\mathbf{III}$}}
\usefont{T1}{ptm}{m}{n}
\rput(4.325625,0.8204687){$L_p$}
\psline[linewidth=0.01cm,linestyle=dashed,dash=0.16cm 0.16cm](0.3353125,-2.1495314)(8.095312,-2.1695313)
\psline[linewidth=0.01cm,linestyle=dashed,dash=0.16cm 0.16cm](0.3553125,-0.28953126)(8.115313,-0.30953124)
\psline[linewidth=0.01cm,linestyle=dashed,dash=0.16cm 0.16cm](0.3353125,-2.7495313)(8.095312,-2.7695312)
\usefont{T1}{ptm}{m}{n}
\rput(0.16265625,-2.7195313){$x_u$}
\psframe[linewidth=0.01,linecolor=color4560b,dimen=outer,fillstyle=solid,fillcolor=color4560b](0.6753125,2.6504688)(0.3353125,2.6204689)
\usefont{T1}{ptm}{m}{n}
\rput(0.1678125,2.6604688){$x_e$}
\psline[linewidth=0.010cm,linestyle=dashed,dash=0.16cm](1.5553125,-2.1495314)(1.5553125,-3.1695313)
\psline[linewidth=0.010cm,linestyle=dashed,dash=0.16cm](7.1153126,-2.1495314)(7.1153126,-3.1695313)
\usefont{T1}{ptm}{m}{n}
\rput(1.5323437,-3.3195312){$t_0$}
\usefont{T1}{ptm}{m}{n}
\rput(7.137656,-3.2795312){$t_c$}
\end{pspicture} 
}
\label{fig:xtdiag}
\caption{$x-t$ diagram for a single intersection}
\end{figure}
In the figure, vehicles 2 to 8 experience some level of delay at the intersection. If the upstream VTL is placed at $x_c$, delayed vehicles 5 to 8 would report the free flow travel time between $x_c$ and $x_d$, and VTLs would not be capturing all the vehicles delayed at the intersection. If the upstream VTL is placed at $x_a$ or $x_b$, all the delayed vehicles are classified as such. However, by placing the upstream VTL at $x_a$ no additional information is being collected with respect to location $x_b$. In fact, the delay with respect to the free flow travel time is less significant as the upstream VTL is moved further upstream $x_b$. Therefore, the best location for the upstream VTL --for our purposes-- is at $x_b$, which corresponds to the maximum extend of the queue.

%The maximum extend of the queue is $L_Q=x_j^u-x_b$, and can be obtained geometrically from the figure: $$L_Q=\frac{u_w\cdot u_s\cdot R}{u_w-u_s}$$, where $R$ is the length of the red period. However, signal timing is rarely known (and it could also varies from cycle to cycle). By moving the upstream VTL, location $x_b$ can be inferred.

For a real intersection located in Berkeley, California, Table~\ref{tab:values} shows the position of the VTLs and the intersection with respect to the further upstream VTL. The length of different sections are also shown.
\begin{table}
  \centering
  \caption{Values (meters).}\label{tab:values}
\begin{tabular}{|c|r|c|r|}
  \hline
  $x_a$ & 0 & $s_a = x_d-x_a$ & 240 \\
  $x_b$ & 40 & $s_b = x_d-x_b$ & 200 \\
  $x_c$ & 88 & $s_c = x_d-x_c$ & 152 \\
  $x_j^u$ & 102 & $x_j^u-x_b$ & 62 \\
  $x_j^d$ & 140 & $x_j^d-x_j^u$ & 38 \\
  $x_d$ & 240 & $x_d - x_j^d$ & 100 \\
  \hline
\end{tabular}
\end{table}

Delay experienced by all vehicles was computed for the sections $s_a$, $s_b$, and $s_c$. The delay experienced by vehicle $i$ is given by $w_i=tt_i-tt_f$. The free flow travel time $tt_f$ is computed assuming a free flow speed of $v_f=36$ kph, which gives 24, 20 and 15 seconds for each section. A vehicle is considered as delayed if $w_i\geqslant 10$ seconds. In section $s_c$ 47 out of 130 vehicles are considered as delayed, while this number goes up to 71 for sections $s_b$ and $s_a$. The mean absolute difference of delays with respect to $s_b$ is 9.1 and 1.7 seconds for sections $s_c$ and $s_a$, respectively (see Figure~\ref{fig:diff_delay}, which shows the difference in delays). These figures confirm that by placing the upstream VTL to close to the intersection ($x_a$), several vehicles that experience delay at the intersection are not considered as such. They also show that no more useful information is obtained by placing the upstream VTL further upstream from $x_b$.
\begin{figure}[!h]
  \centering
  \includegraphics[width=.5\textwidth]{diff_delay.eps}\\
  \caption{Delay differences of $s_a$ and $s_c$ with respect to $s_b$ (in seconds).}
  \label{fig:diff_delay}
\end{figure}

Note that in case of over-saturation (i.e. when vehicles are stopped for more than one red period before they are able to cross the intersection), the placement defined will not provide information to identified these periods. In this case, moving the upstream VTL further upstream $x_b$ would allow the identification of over-saturated periods, since it would capture the difference in delays between under- and over-saturated periods. In the example shown before, suppose the upstream VTL is located at $x_c$. In the under-saturated case, delays for sections $s_a$ and $s_b$ are similar, because there is no delay between $x_a$ and $x_b$. If the intersection is over-saturated, the maximum extend of the queue is upstream $x_b$. Thus, at least part of the section between $x_a$ and $x_b$ is queued, which means that some delay is being introduced in that section. Delays experienced in section $s_a$ are no longer similar to those experienced in section $s_b$. Therefore, over-saturated periods can be identified in this way.

\begin{itemize}
	\item Importance of placing the VTLs
	\item Capturing the variance upstream of the intersection
	\item Optimal placement in the sense of capturing the queue length upstream of the intersection
	\item Discussion based on travel times, pace and average speed
	\item Effect of oversaturation
\end{itemize}


\section{Estimation method}

\subsection{Cluster analysis}
	\begin{itemize}
		\item Clustering and time series analysis of the travel times, pace and average speed variables
		\item Effect of VTL placement and queue oversaturation on the separation of clusters
		\item Learning inter-cluster Markov transition probabilities matrices
		\item Comment on stationarity
	\end{itemize}

\subsection{Single intersection or link delay model}
	\begin{itemize}	
		\item Probabilistic state as a proxy for intersection delay: 3-4 "hidden" states
		\item Maximum likelihood estimation of the state given the data
		\item Effect of missing/sparse missing data
	\end{itemize}

\subsection{Network travel time model: discrete estimation}
	\begin{itemize}
		\item Extending single intersection delay model to superlinks, route and network levels
		\item Maximum likelihood estimation of the unknown states describing the state of the each of the intersections on the super-link, route or network.
		\item MCMC/Kalman type estimation method and its scalability
	\end{itemize}

\subsection{Extension to hybrid estimation}
	\begin{itemize}
		\item Discrete and continuous estimation
		\item Main bottlenecks in terms of meta-data such as signal timing, fundamental diagram parameters etc.
		\item Potential for extension
	\end{itemize}
	

\section{Results and discussion}

\subsection{Berkeley/SFO/NY tests}
	\begin{itemize}
		\item Brief description of data collection method
		\item Important points from a practical point of view: such as interference in urban setting etc
	\end{itemize}
	
\subsection{Results}
	\begin{itemize}
		\item Results of the estimation method for the Berkeley and SFO data
		\item Discussion and comparison w.r.t to naive estimation method (averaging)
	\end{itemize}
	

\section{Concluding remarks}

	\subsection{Lessons learned}
	
	\subsection{Future challenges}
		\begin{itemize}
			\item Integration with other data sources
			\item Large scale deployment
			\item Incorporating historical data
		\end{itemize}
%The \textit{proceedings} are the records of a conference.
%ACM seeks to give these conference by-products a uniform,
%high-quality appearance.  To do this, ACM has some rigid
%requirements for the format of the proceedings documents: there
%is a specified format (balanced  double columns), a specified
%set of fonts (Arial or Helvetica and Times Roman) in
%certain specified sizes (for instance, 9 point for body copy),
%a specified live area (18 $\times$ 23.5 cm [7" $\times$ 9.25"]) centered on
%the page, specified size of margins (2.54cm [1"] top and
%bottom and 1.9cm [.75"] left and right; specified column width
%(8.45cm [3.33"]) and gutter size (.083cm [.33"]).
%
%The good news is, with only a handful of manual
%settings\footnote{Two of these, the {\texttt{\char'134 numberofauthors}}
%and {\texttt{\char'134 alignauthor}} commands, you have
%already used; another, {\texttt{\char'134 balancecolumns}}, will
%be used in your very last run of \LaTeX\ to ensure
%balanced column heights on the last page.}, the \LaTeX\ document
%class file handles all of this for you.
%
%The remainder of this document is concerned with showing, in
%the context of an ``actual'' document, the \LaTeX\ commands
%specifically available for denoting the structure of a
%proceedings paper, rather than with giving rigorous descriptions
%or explanations of such commands.
%
%\section{The {\secit Body} of The Paper}
%Typically, the body of a paper is organized
%into a hierarchical structure, with numbered or unnumbered
%headings for sections, subsections, sub-subsections, and even
%smaller sections.  The command \texttt{{\char'134}section} that
%precedes this paragraph is part of such a
%hierarchy.\footnote{This is the second footnote.  It
%starts a series of three footnotes that add nothing
%informational, but just give an idea of how footnotes work
%and look. It is a wordy one, just so you see
%how a longish one plays out.} \LaTeX\ handles the numbering
%and placement of these headings for you, when you use
%the appropriate heading commands around the titles
%of the headings.  If you want a sub-subsection or
%smaller part to be unnumbered in your output, simply append an
%asterisk to the command name.  Examples of both
%numbered and unnumbered headings will appear throughout the
%balance of this sample document.
%
%Because the entire article is contained in
%the \textbf{document} environment, you can indicate the
%start of a new paragraph with a blank line in your
%input file; that is why this sentence forms a separate paragraph.
%
%\subsection{Type Changes and {\subsecit Special} Characters}
%We have already seen several typeface changes in this sample.  You
%can indicate italicized words or phrases in your text with
%the command \texttt{{\char'134}textit}; emboldening with the
%command \texttt{{\char'134}textbf}
%and typewriter-style (for instance, for computer code) with
%\texttt{{\char'134}texttt}.  But remember, you do not
%have to indicate typestyle changes when such changes are
%part of the \textit{structural} elements of your
%article; for instance, the heading of this subsection will
%be in a sans serif\footnote{A third footnote, here.
%Let's make this a rather short one to
%see how it looks.} typeface, but that is handled by the
%document class file. Take care with the use
%of\footnote{A fourth, and last, footnote.}
%the curly braces in typeface changes; they mark
%the beginning and end of
%the text that is to be in the different typeface.
%
%You can use whatever symbols, accented characters, or
%non-English characters you need anywhere in your document;
%you can find a complete list of what is
%available in the \textit{\LaTeX\
%User's Guide}\cite{Lamport:LaTeX}.
%
%\subsection{Math Equations}
%You may want to display math equations in three distinct styles:
%inline, numbered or non-numbered display.  Each of
%the three are discussed in the next sections.
%
%\subsubsection{Inline (In-text) Equations}
%A formula that appears in the running text is called an
%inline or in-text formula.  It is produced by the
%\textbf{math} environment, which can be
%invoked with the usual \texttt{{\char'134}begin. . .{\char'134}end}
%construction or with the short form \texttt{\$. . .\$}. You
%can use any of the symbols and structures,
%from $\alpha$ to $\omega$, available in
%\LaTeX\cite{Lamport:LaTeX}; this section will simply show a
%few examples of in-text equations in context. Notice how
%this equation: \begin{math}\lim_{n\rightarrow \infty}x=0\end{math},
%set here in in-line math style, looks slightly different when
%set in display style.  (See next section).
%
%\subsubsection{Display Equations}
%A numbered display equation -- one set off by vertical space
%from the text and centered horizontally -- is produced
%by the \textbf{equation} environment. An unnumbered display
%equation is produced by the \textbf{displaymath} environment.
%
%Again, in either environment, you can use any of the symbols
%and structures available in \LaTeX; this section will just
%give a couple of examples of display equations in context.
%First, consider the equation, shown as an inline equation above:
%\begin{equation}\lim_{n\rightarrow \infty}x=0\end{equation}
%Notice how it is formatted somewhat differently in
%the \textbf{displaymath}
%environment.  Now, we'll enter an unnumbered equation:
%\begin{displaymath}\sum_{i=0}^{\infty} x + 1\end{displaymath}
%and follow it with another numbered equation:
%\begin{equation}\sum_{i=0}^{\infty}x_i=\int_{0}^{\pi+2} f\end{equation}
%just to demonstrate \LaTeX's able handling of numbering.
%
%\subsection{Citations}
%Citations to articles \cite{bowman:reasoning,
%clark:pct, braams:babel, herlihy:methodology},
%conference proceedings \cite{clark:pct} or
%books \cite{salas:calculus, Lamport:LaTeX} listed
%in the Bibliography section of your
%article will occur throughout the text of your article.
%You should use BibTeX to automatically produce this bibliography;
%you simply need to insert one of several citation commands with
%a key of the item cited in the proper location in
%the \texttt{.tex} file \cite{Lamport:LaTeX}.
%The key is a short reference you invent to uniquely
%identify each work; in this sample document, the key is
%the first author's surname and a
%word from the title.  This identifying key is included
%with each item in the \texttt{.bib} file for your article.
%
%The details of the construction of the \texttt{.bib} file
%are beyond the scope of this sample document, but more
%information can be found in the \textit{Author's Guide},
%and exhaustive details in the \textit{\LaTeX\ User's
%Guide}\cite{Lamport:LaTeX}.
%
%This article shows only the plainest form
%of the citation command, using \texttt{{\char'134}cite}.
%This is what is stipulated in the SIGS style specifications.
%No other citation format is endorsed or supported.
%
%\subsection{Tables}
%Because tables cannot be split across pages, the best
%placement for them is typically the top of the page
%nearest their initial cite.  To
%ensure this proper ``floating'' placement of tables, use the
%environment \textbf{table} to enclose the table's contents and
%the table caption.  The contents of the table itself must go
%in the \textbf{tabular} environment, to
%be aligned properly in rows and columns, with the desired
%horizontal and vertical rules.  Again, detailed instructions
%on \textbf{tabular} material
%is found in the \textit{\LaTeX\ User's Guide}.
%
%Immediately following this sentence is the point at which
%Table 1 is included in the input file; compare the
%placement of the table here with the table in the printed
%dvi output of this document.
%
%\begin{table}
%\centering
%\caption{Frequency of Special Characters}
%\begin{tabular}{|c|c|l|} \hline
%Non-English or Math&Frequency&Comments\\ \hline
%\O & 1 in 1,000& For Swedish names\\ \hline
%$\pi$ & 1 in 5& Common in math\\ \hline
%\$ & 4 in 5 & Used in business\\ \hline
%$\Psi^2_1$ & 1 in 40,000& Unexplained usage\\
%\hline\end{tabular}
%\end{table}
%
%To set a wider table, which takes up the whole width of
%the page's live area, use the environment
%\textbf{table*} to enclose the table's contents and
%the table caption.  As with a single-column table, this wide
%table will ``float" to a location deemed more desirable.
%Immediately following this sentence is the point at which
%Table 2 is included in the input file; again, it is
%instructive to compare the placement of the
%table here with the table in the printed dvi
%output of this document.
%
%
%\begin{table*}
%\centering
%\caption{Some Typical Commands}
%\begin{tabular}{|c|c|l|} \hline
%Command&A Number&Comments\\ \hline
%\texttt{{\char'134}alignauthor} & 100& Author alignment\\ \hline
%\texttt{{\char'134}numberofauthors}& 200& Author enumeration\\ \hline
%\texttt{{\char'134}table}& 300 & For tables\\ \hline
%\texttt{{\char'134}table*}& 400& For wider tables\\ \hline\end{tabular}
%\end{table*}
%% end the environment with {table*}, NOTE not {table}!
%
%\subsection{Figures}
%Like tables, figures cannot be split across pages; the
%best placement for them
%is typically the top or the bottom of the page nearest
%their initial cite.  To ensure this proper ``floating'' placement
%of figures, use the environment
%\textbf{figure} to enclose the figure and its caption.
%
%This sample document contains examples of \textbf{.eps}
%and \textbf{.ps} files to be displayable with \LaTeX.  More
%details on each of these is found in the \textit{Author's Guide}.
%
%\begin{figure}
%\centering
%\epsfig{file=fly.eps}
%\caption{A sample black and white graphic (.eps format).}
%\end{figure}
%
%\begin{figure}
%\centering
%\epsfig{file=fly.eps, height=1in, width=1in}
%\caption{A sample black and white graphic (.eps format)
%that has been resized with the \texttt{epsfig} command.}
%\end{figure}
%
%
%As was the case with tables, you may want a figure
%that spans two columns.  To do this, and still to
%ensure proper ``floating'' placement of tables, use the environment
%\textbf{figure*} to enclose the figure and its caption.
%\begin{figure*}
%\centering
%\epsfig{file=flies.eps}
%\caption{A sample black and white graphic (.eps format)
%that needs to span two columns of text.}
%\end{figure*}
%and don't forget to end the environment with
%{figure*}, not {figure}!
%
%Note that either {\textbf{.ps}} or {\textbf{.eps}} formats are
%used; use
%the \texttt{{\char'134}epsfig} or \texttt{{\char'134}psfig}
%commands as appropriate for the different file types.
%
%\begin{figure}
%\centering
%\psfig{file=rosette.ps, height=1in, width=1in,}
%\caption{A sample black and white graphic (.ps format) that has
%been resized with the \texttt{psfig} command.}
%\vskip -6pt
%\end{figure}
%
%\subsection{Theorem-like Constructs}
%Other common constructs that may occur in your article are
%the forms for logical constructs like theorems, axioms,
%corollaries and proofs.  There are
%two forms, one produced by the
%command \texttt{{\char'134}newtheorem} and the
%other by the command \texttt{{\char'134}newdef}; perhaps
%the clearest and easiest way to distinguish them is
%to compare the two in the output of this sample document:
%
%This uses the \textbf{theorem} environment, created by
%the\linebreak\texttt{{\char'134}newtheorem} command:
%\newtheorem{theorem}{Theorem}
%\begin{theorem}
%Let $f$ be continuous on $[a,b]$.  If $G$ is
%an antiderivative for $f$ on $[a,b]$, then
%\begin{displaymath}\int^b_af(t)dt = G(b) - G(a).\end{displaymath}
%\end{theorem}
%
%The other uses the \textbf{definition} environment, created
%by the \texttt{{\char'134}newdef} command:
%\newdef{definition}{Definition}
%\begin{definition}
%If $z$ is irrational, then by $e^z$ we mean the
%unique number which has
%logarithm $z$: \begin{displaymath}{\log e^z = z}\end{displaymath}
%\end{definition}
%
%Two lists of constructs that use one of these
%forms is given in the
%\textit{Author's  Guidelines}.
%
%There is one other similar construct environment, which is
%already set up
%for you; i.e. you must \textit{not} use
%a \texttt{{\char'134}newdef} command to
%create it: the \textbf{proof} environment.  Here
%is a example of its use:
%\begin{proof}
%Suppose on the contrary there exists a real number $L$ such that
%\begin{displaymath}
%\lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} = L.
%\end{displaymath}
%Then
%\begin{displaymath}
%l=\lim_{x\rightarrow c} f(x)
%= \lim_{x\rightarrow c}
%\left[ g{x} \cdot \frac{f(x)}{g(x)} \right ]
%= \lim_{x\rightarrow c} g(x) \cdot \lim_{x\rightarrow c}
%\frac{f(x)}{g(x)} = 0\cdot L = 0,
%\end{displaymath}
%which contradicts our assumption that $l\neq 0$.
%\end{proof}
%
%Complete rules about using these environments and using the
%two different creation commands are in the
%\textit{Author's Guide}; please consult it for more
%detailed instructions.  If you need to use another construct,
%not listed therein, which you want to have the same
%formatting as the Theorem
%or the Definition\cite{salas:calculus} shown above,
%use the \texttt{{\char'134}newtheorem} or the
%\texttt{{\char'134}newdef} command,
%respectively, to create it.
%
%\subsection*{A {\secit Caveat} for the \TeX\ Expert}
%Because you have just been given permission to
%use the \texttt{{\char'134}newdef} command to create a
%new form, you might think you can
%use \TeX's \texttt{{\char'134}def} to create a
%new command: \textit{Please refrain from doing this!}
%Remember that your \LaTeX\ source code is primarily intended
%to create camera-ready copy, but may be converted
%to other forms -- e.g. HTML. If you inadvertently omit
%some or all of the \texttt{{\char'134}def}s recompilation will
%be, to say the least, problematic.
%
%\section{Conclusions}
%This paragraph will end the body of this sample document.
%Remember that you might still have Acknowledgments or
%Appendices; brief samples of these
%follow.  There is still the Bibliography to deal with; and
%we will make a disclaimer about that here: with the exception
%of the reference to the \LaTeX\ book, the citations in
%this paper are to articles which have nothing to
%do with the present subject and are used as
%examples only.
%%\end{document}  % This is where a 'short' article might terminate
%
%%ACKNOWLEDGMENTS are optional
%\section{Acknowledgments}
%This section is optional; it is a location for you
%to acknowledge grants, funding, editing assistance and
%what have you.  In the present case, for example, the
%authors would like to thank Gerald Murray of ACM for
%his help in codifying this \textit{Author's Guide}
%and the \textbf{.cls} and \textbf{.tex} files that it describes.

%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\bibliographystyle{abbrv}
%\bibliography{sigproc}  % sigproc.bib is the name of the Bibliography in this case
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns
\appendix
%Appendix A
%\section{Headings in Appendices}
%The rules about hierarchical headings discussed above for
%the body of the article are different in the appendices.
%In the \textbf{appendix} environment, the command
%\textbf{section} is used to
%indicate the start of each Appendix, with alphabetic order
%designation (i.e. the first is A, the second B, etc.) and
%a title (if you include one).  So, if you need
%hierarchical structure
%\textit{within} an Appendix, start with \textbf{subsection} as the
%highest level. Here is an outline of the body of this
%document in Appendix-appropriate form:
%\subsection{Introduction}
%\subsection{The Body of the Paper}
%\subsubsection{Type Changes and  Special Characters}
%\subsubsection{Math Equations}
%\paragraph{Inline (In-text) Equations}
%\paragraph{Display Equations}
%\subsubsection{Citations}
%\subsubsection{Tables}
%\subsubsection{Figures}
%\subsubsection{Theorem-like Constructs}
%\subsubsection*{A Caveat for the \TeX\ Expert}
%\subsection{Conclusions}
%\subsection{Acknowledgments}
%\subsection{Additional Authors}
%This section is inserted by \LaTeX; you do not insert it.
%You just add the names and information in the
%\texttt{{\char'134}additionalauthors} command at the start
%of the document.
%\subsection{References}
%Generated by bibtex from your ~.bib file.  Run latex,
%then bibtex, then latex twice (to resolve references)
%to create the ~.bbl file.  Insert that ~.bbl file into
%the .tex source file and comment out
%the command \texttt{{\char'134}thebibliography}.
%% This next section command marks the start of
%% Appendix B, and does not continue the present hierarchy
%\section{More Help for the Hardy}
%The sig-alternate.cls file itself is chock-full of succinct
%and helpful comments.  If you consider yourself a moderately
%experienced to expert user of \LaTeX, you may find reading
%it useful but please remember not to change it.
%%\balancecolumns % GM June 2007
%% That's all folks!
%
\bibliographystyle{plain}
%%plain or alpha abbr
\bibliography{lagrange}
\end{document}
